/**
题目:
    给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。

 

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：

输入：s = "0000"
输出：["0.0.0.0"]
示例 3：

输入：s = "1111"
输出：["1.1.1.1"]
示例 4：

输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]
示例 5：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
 

提示：

0 <= s.length <= 3000
s 仅由数字组成


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-ip-addresses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路: 回溯
*/
class Solution {
public:
vector<string> res;
    vector<string> restoreIpAddresses(string s) {
        vector<int> pos;
        dfs(s,1,s.size()-1,pos);
        return res;
    }
    bool valid(string&ip1,string&ip2,string&ip3,string&ip4){
         auto adjust=[](string ip){
             if(ip.empty()){
                 return false;
             }
             if(ip[0]=='0'&&ip.size()>1){
                 return false;
             }
            int tmp=0;
             for(int i=0;i<ip.size();i++){
                 if(ip[i]<='9'&&ip[i]>='0'){
                     double result=tmp;
                     if(result>INT_MAX/10.0){
                         return false;
                     }else if(result*10>INT_MAX-ip[i]+'0'){
                         return false;
                     }
                    tmp=tmp*10+ip[i]-'0';
                 }else{
                     return false;
                 }
             }
             return tmp>=0&&tmp<=255;
         };
         return adjust(ip1)&&adjust(ip2)&&adjust(ip3)&&adjust(ip4);
    }
    void dfs(string&s,int index,int len,vector<int>&pos){
        if(pos.size()==3){
            //校验是否是合格的ip地址
            string ip1=s.substr(0,pos[0]);
            string ip2=s.substr(pos[0],pos[1]-pos[0]);
            string ip3=s.substr(pos[1],pos[2]-pos[1]);
            string ip4=s.substr(pos[2],s.size()-pos[2]);
            if(valid(ip1,ip2,ip3,ip4)){
                ip1+="."+ip2+"."+ip3+"."+ip4;
                res.push_back(ip1);
            }
            return ;
        }
        for(int i=index;i<=len;i++){
            pos.push_back(i);
            dfs(s,i+1,len,pos);
            pos.pop_back();
        }
        return ;
    }
};